/*
  S.M.A.C.K - An operating system kernel
  Copyright (C) 2010,2011 Mattias Holm and Kristian Rietveld
  For licensing and a full list of authors of the kernel, see the files
  COPYING and AUTHORS.
*/

#ifndef KERNEL__LIST_H
#define KERNEL__LIST_H

/*
  Based on code from Open Orbit (c) Mattias Holm.
  This file has kindly been relicensed using the BSD license.
*/

#define LIST_HEAD(TYPE) struct { struct TYPE *head; struct TYPE *tail; }
#define LIST_FIRST(LIST) ((LIST).head)
#define LIST_LAST(LIST) ((LIST).tail)

#define LIST_ENTRY(TYPE) struct { struct TYPE *next; struct TYPE *prev; }

#define LIST_CONCAT(LISTA, LISTB, ENTRY)                                \
  do {                                                                  \
    if (LIST_EMPTY(LISTA)) {                                            \
      LIST_FIRST(LISTA) = LIST_FIRST(LISTB);                            \
      LIST_LAST(LISTA) = LIST_LAST(LISTB);                              \
    } else if (!LIST_EMPTY(LISTB)) {                                    \
      LIST_LAST(LISTA)->ENTRY.next = LIST_FIRST(LISTB);                 \
      LIST_FIRST(LISTB)->ENTRY.prev = LIST_LAST(LISTA);                 \
      LIST_LAST(LISTA) = LIST_LAST(LISTB);                              \
    }                                                                   \
    LIST_FIRST(LISTB) = NULL;                                           \
    LIST_LAST(LISTB) = NULL;                                            \
  } while (0)

#define LIST_APPEND(LIST,ELEM,ENTRY)            \
  do {                                          \
    if (LIST_LAST(LIST)) {                      \
      LIST_LAST(LIST)->ENTRY.next = (ELEM);       \
      (ELEM)->ENTRY.prev = LIST_LAST(LIST);       \
      LIST_LAST(LIST) = (ELEM);                   \
      (ELEM)->ENTRY.next = NULL;                  \
    } else {                                    \
      LIST_FIRST(LIST) = (ELEM);                  \
      LIST_LAST(LIST) = (ELEM);                   \
      (ELEM)->ENTRY.next = NULL;                  \
      (ELEM)->ENTRY.prev = NULL;                  \
    }                                           \
  } while (0)

#define LIST_PREPEND(LIST,ELEM,ENTRY)            \
  do {                                           \
    if (LIST_FIRST(LIST)) {                      \
      LIST_FIRST(LIST)->ENTRY.prev = (ELEM);     \
      (ELEM)->ENTRY.next = LIST_FIRST(LIST);     \
      LIST_FIRST(LIST) = (ELEM);                 \
      (ELEM)->ENTRY.prev = NULL;                 \
    } else {                                     \
      LIST_FIRST(LIST) = (ELEM);                 \
      LIST_LAST(LIST) = (ELEM);                  \
      (ELEM)->ENTRY.next = NULL;                 \
      (ELEM)->ENTRY.prev = NULL;                 \
    }                                            \
  } while (0)

#define LIST_EMPTY(lhead) ((lhead).head == NULL)
#define LIST_NEXT(elem, field) ((elem)->field.next)
#define LIST_PREV(elem, field) ((elem)->field.prev)

#define LIST_FOREACH(val, lhead, field) \
for (val = (lhead).head ; val != NULL ; val = LIST_NEXT(val, field))


#define LIST_INSERT_AFTER(LIST, POS, ELEM, ENTRY)                       \
  do {                                                                  \
    (ELEM)->ENTRY.prev = (POS);                                         \
    (ELEM)->ENTRY.next = (POS)->ENTRY.next;                             \
    if ((POS)->ENTRY.next) (POS)->ENTRY.next->ENTRY.prev = (ELEM);      \
    (POS)->ENTRY.next = (ELEM);                                         \
    if (LIST_LAST(LIST) == POS) LIST_LAST(LIST) = (ELEM);               \
  } while (0)


#define LIST_INSERT_BEFORE(LIST, POS, ELEM, ENTRY)                      \
  do {                                                                  \
    (ELEM)->ENTRY.next = (POS);                                         \
    (ELEM)->ENTRY.prev = (POS)->ENTRY.prev;                             \
    if (POS->ENTRY.prev) POS->ENTRY.prev->ENTRY.next = (ELEM);          \
    (POS)->ENTRY.prev = ELEM;                                           \
    if (LIST_FIRST(LIST) == POS) LIST_FIRST(LIST) = (ELEM);             \
  } while (0)


#define LIST_REMOVE(LIST, POS, ENTRY)                                   \
  do {                                                                  \
    if (LIST_FIRST(LIST) == (POS)) LIST_FIRST(LIST) = (POS)->ENTRY.next;    \
    if (LIST_LAST(LIST) == (POS)) LIST_LAST(LIST) = (POS)->ENTRY.prev;      \
    if ((POS)->ENTRY.prev) (POS)->ENTRY.prev->ENTRY.next = (POS)->ENTRY.next; \
    if ((POS)->ENTRY.next) (POS)->ENTRY.next->ENTRY.prev = (POS)->ENTRY.prev; \
    (POS)->ENTRY.next = NULL;                                             \
    (POS)->ENTRY.prev = NULL;                                             \
  } while (0)

#define LIST_REMOVE_RANGE(LIST, POSA, POSB, ENTRY)                      \
  do {                                                                  \
    if (LIST_FIRST(LIST) == (POSA)) LIST_FIRST(LIST) = (POSB)->ENTRY.next;  \
    if (LIST_LAST(LIST) == (POSB)) LIST_LAST(LIST) = (POSA)->ENTRY.prev;    \
    if ((POSA)->ENTRY.prev) (POSA)->ENTRY.prev->ENTRY.next = (POSB)->ENTRY.next; \
    if ((POSB)->ENTRY.next) (POSB)->ENTRY.next->ENTRY.prev = (POSA)->ENTRY.prev; \
    (POSB)->ENTRY.next = NULL;                                             \
    (POSA)->ENTRY.prev = NULL;                                             \
  } while (0)

#define LIST_INSERT_RANGE_AFTER(LIST, IPOS, POSA, POSB, ENTRY)          \
  do {                                                                  \
    if (LIST_LAST(LIST) == IPOS) LIST_LAST(LIST) = (POSB);                \
    else (IPOS)->ENTRY.next->prev = (POSB);                                 \
    (IPOS)->ENTRY.next = (POSA);                                            \
    (POSA)->ENTRY.prev = (IPOS);                                            \
  } while (0)

#define LIST_APPEND_RANGE(LIST, POSA, POSB, ENTRY)          \
  do {                                          \
    if (LIST_LAST(LIST)) {                      \
      LIST_LAST(LIST)->ENTRY.next = (POSA);       \
      (POSA)->ENTRY.prev = LIST_LAST(LIST);       \
      LIST_LAST(LIST) = (POSB);                   \
      (POSB)->ENTRY.next = NULL;                  \
    } else {                                    \
      LIST_FIRST(LIST) = (POSA);                  \
      LIST_LAST(LIST) = (POSB);                   \
      (POSB)->ENTRY.next = NULL;                  \
      (POSA)->ENTRY.prev = NULL;                  \
    }                                           \
  } while (0)


#define LIST_HEAD_INIT  {NULL, NULL}

#endif /* ! KERNEL__LIST_H */
